//
//  ThreeSequence.m
//  iOS-Learning-Demo
//
//  Created by yuan xiaodong on 2022/3/29.
//  Copyright © 2022 yuan. All rights reserved.
//

#import "ThreeSequence.h"
#import "BinaryTree.h"

@implementation ThreeSequence

//TODO:重建二叉树
/**
 
 输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
 输入：
 
 前序遍历 preorder = [3,9,20,15,7]
 中序遍历 inorder = [9,3,15,20,7]
 
 3
/ \
9  20
 /  \
15   7

限制
0 <= 节点个数 <= 5000
 */

+ (void)buildTree{
    NSArray *preorder = @[@3,@9,@20,@15,@7];
    NSArray *inorder = @[@9,@3,@15,@20,@7];
    
    BinaryTreeNode *node = [self help:preorder l1:0 r1:preorder.count - 1 inOrder:inorder l2:0 r2:inorder.count - 1];
    NSLog(@"%@",node);
}

+ (BinaryTreeNode *)help:(NSArray *)preOrder l1:(NSInteger)l1 r1:(NSInteger)r1 inOrder:(NSArray *)inOrder l2:(NSInteger)l2 r2:(NSInteger)r2{
    if (l1 > r1 || l2 > r2) return nil;
    NSInteger i = l2;
    while (inOrder[i] != preOrder[l1]) {//在中序数组中查找根节点
        i++;
    }
    BinaryTreeNode *root = BinaryTreeNode.new;
    root.value = [preOrder[l1] intValue];
    root.leftNode = [self help:preOrder l1:l1+1 r1:l1+i-l2 inOrder:inOrder l2:l2 r2:i-1];
    root.rightNode = [self help:preOrder l1:l1+i-l2+1 r1:r1 inOrder:inOrder l2:i+1 r2:r2];
    return root;
}

@end
